package com.yang.Dp.bags;

/**
 * @Author: yang
 * @Description:
 * 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
 * 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
 * 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
 * @Date: Created in 18:03 2022/8/10
 * @Modified By:
 */
public class LeetCode474 {
}
class LeetCode474Solution {
    // 本题的解题重点 把mn看做是一个二维的背包容量 dp[m][n]
    // 集合中的所有字符为 不同的物品
    // 1.所以有 dp[i][j] 表达 最多有 i j 个0 1的 字符子集最大数量
    // 2.递推公式 dp[i][j] = Math.max(dp[i][j], dp[i - zeroNums][j - OneNums] + 1)
    // 3.初始化 都初始化为0
    public int findMaxForm(String[] strs, int m, int n) {
        int dp[][] = new int[m + 1][n + 1];

        // 这个for循环就是相当于遍历物品
        for(String str : strs){
            int oneNums = 0, zeroNums = 0;
            for(char c : str.toCharArray()){
                if(c == '0'){
                    zeroNums ++;
                }else{
                    oneNums ++;
                }
            }
            // 这里是在遍历容量 但是因为容量是二维的所以要多个for循环遍历
            for(int i = m; i >= zeroNums; i--){
                for(int j = n; j >= oneNums; j--){
                    // 当前最大字符子集的数量受到前一个状态的影响(当前有 x个1 y个0  那么就是dp[i - y][j - x] + 1)
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroNums][j - oneNums] + 1);
                }
            }
        }
        return dp[m][n];
    }
}
